import math

def memoize( f ):
  d = {}
  def closure( *args ):
    if args not in d:
      d[args] = f( *args )
    return d[args]
  return closure

def prob1():
  return sum( filter( lambda i: not i % 3 or not i % 5, range( 1, 1000 ) ) )
  
fibs = [ 1, 1 ]
def fibsTo( n ):
  while fibs[-1] < n:
    fibs.append( fibs[-1] + fibs[-2] )
  return fibs[:-1]
  
def isEven( n ):
  return n % 2 == 0
  
def prob2():
  return sum( filter( isEven, fibsTo( 4000000 ) ) )

@memoize
def isPrime( n ):
  n = abs( n )
  if n < 1:
    return False
  elif n == 1:
    return True
  else:
    i = 2
    while i * i <= n:
      if not n % i:
        return False
      i += 1
    return True

def primeFactors( n ):
  factors = []
  while not isPrime( n ):
    i = 2
    while i < n:
      if not n % i and isPrime( i ):
        factors.append( i )
        n /= i
        break
      i += 1
  factors.append( n )
  return factors
  
def prob3():
  return max( primeFactors( 600851475143 ) )

def isPalindrome( s ):
  for i in range( len( s ) / 2 ):
    if s[i] != s[len(s)-1-i]:
      return False
  return True
  
def getProducts( min, max ):
  products = []
  for i in range( min, max ):
    for j in range( i, max ):
      products.append( i * j )
  return products
  
def prob4():
  return max( map( int, filter( isPalindrome, map( str, getProducts( 100, 1000 ) ) ) ) )

def divisibleByRange( min, max, n ):
  for i in range( min, max ):
    if n % i:
      return False
  return True
  
def prob5():
  i = 1
  while True:
    if divisibleByRange( 1, 21, i ):
      return i
    i += 1

def prob6():
  n = 100
  s = sum( range( n + 1 ) )
  return s * s - sum( [ i * i for i in range( n + 1 ) ] )

def getPrimes( n ):
  primes = [2]
  while len( primes ) < n:
    p = primes[-1] + 1
    while not isPrime( p ):
      p += 1
    primes.append( p )
  return primes
  
def prob7():
  return getPrimes( 10001 )[-1]
  
def product( l ):
  n = 1
  for i in l:
    n *= i
  return n

def prob8():
  s = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
  l = 5
  return max( [ product( map( int, s[i:i+l] ) ) for i in range( len( s ) - l ) ] )

def isPythTriplet( a, b, c ):
  return a < b and b < c and a * a + b * b == c * c
  
def adders( n ):
  return [ ( i, n - i ) for i in range( n + 1 ) ]
  
def prob9():
  n = 1000
  for a, bc in adders( n ):
    for b, c in adders( bc ):
      if isPythTriplet( a, b, c ):
        return a * b * c

def prob10():
  n = 2
  s = 0
  while n < 2000000:
    if isPrime( n ):
      s += n
    n += 1
  return s
  
def prob11():
  s = '''08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'''
  l = 4
  grid = [ map( int, line.split() ) for line in s.split( '\n' ) ]
  w = len( grid[0] )
  h = len( grid )
  max = -1
  for i in range( w ):
    for j in range( h ):
      for di in ( -1, 0, 1 ):
        for dj in ( -1, 0, 1 ):
          maxi = i + l * di - 1
          maxj = j + l * dj - 1
          if ( di or dj ) and ( maxi >= 0 and maxi < w and maxj >= 0 and maxj < h ):
            s = product( [ grid[ i + di * k ][ j + dj * k ] for k in range( l ) ] )
            if s > max:
              max = s
  return max
 
def getNumFactors( n ):
  nf = 2
  i = 2
  while i <= n / 2:
    if n % i == 0:
      nf += 1
    i += 1
  return nf
  return filter( lambda i: n % i == 0, range( 1, n + 1 ) )
  
#slow
def prob12():
  i = 1
  n = 1
  f = 0
  while f <= 500:
    i += 1
    n += i
    f = getNumFactors( n )
  return n

def prob13():
  s = '''37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690'''
  return str( sum( map( int, s.split() ) ) )[:10]

collatzLens = { 1: 1 }
def getCollatzLen( n ):
  if n in collatzLens:
    return collatzLens[n]
  else:
    if n % 2:
      c = 3 * n + 1
    else:
      c = n / 2
    l = 1 + getCollatzLen( c )
    collatzLens[n] = l
    return l
  
def prob14():
  assert 10 == getCollatzLen( 13 )
  return max( range( 1, 1000000 ), key = getCollatzLen )

@memoize
def getLatticePaths( n, m ):
  if n == 0 and m == 0:
    return 1
  else:
    p = 0
    if n > 0:
      p += getLatticePaths( n - 1, m )
    if m > 0:
      p += getLatticePaths( n, m - 1 )
    return p
  
def prob15():
  assert 6 == getLatticePaths( 2, 2 )
  return getLatticePaths( 20, 20 )

def prob16():
  return sum( map( int, str( 2 ** 1000 ) ) )

def numToWord( n ):
  assert n <= 1000, str( n )
  if n == 1000:
    return 'onethousand'
  elif n >= 100:
    if n % 100:
      return numToWord( n / 100 ) + 'hundredand' + numToWord( n % 100 )
    else:
      return numToWord( n / 100 ) + 'hundred'
  elif n > 10 and n < 20:
    return ( 'eleven', 'twelve', 'thirteen', 'fourteen', 'fifteen', 'sixteen', 'seventeen', 'eighteen', 'nineteen' )[ n - 11 ]
  elif n >= 10:
    return ( '', 'ten', 'twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty', 'ninety' )[ n / 10 ] + numToWord( n % 10 )
  else:
    return ( '', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine' )[ n ]

def prob17():
  assert len( numToWord( 342 ) ) == 23
  assert len( numToWord( 115 ) ) == 20
  assert sum( map( len, map( numToWord, range( 1, 6 ) ) ) ) == 19
  return sum( map( len, map( numToWord, range( 1, 1001 ) ) ) )

def subTris( tri ):
  return [ row[:-1] for row in tri[1:] ], [ row[1:] for row in tri[1:] ]
  
def triMaxSum( tri ):
  head = tri[0][0]
  if len( tri ) == 1:
    return head
  else:
    return max( [ head + triMaxSum( sub ) for sub in subTris( tri ) ] )
  
def prob18():
  s = '''75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''
  tri = [ map( int, line.split() ) for line in s.split( '\n' ) ]
  return triMaxSum( tri )

def prob19():
  year = 1901
  month = 1
  date = 1
  day = 2
  numFirstSundays = 0
  
  while year < 2001:
    if date == 1 and day == 7:
      numFirstSundays += 1
    day += 1
    if day > 7:
      day = 1
    date += 1
    if date > 30 and month in ( 4, 6, 9, 11 ):
      month += 1
      date = 1
    elif date > 31 and month in ( 1, 3, 5, 7, 8, 10, 12 ):
      month += 1
      date = 1
    elif date > 28 and month == 2 and ( year % 4 or ( not year % 100 and year % 400 ) ):
      month += 1
      date = 1
    elif date > 29 and month == 2:
      month += 1
      date = 1
    if month > 12:
      year += 1
      month = 1

  assert year == 2001 and month == 1 and date == 1 and day == 1 #jan 1 2001 was a monday
  return numFirstSundays

@memoize
def fac( n ):
  return product( range( 1, n + 1 ) )
  
def facSum( n ):
  return sum( map( int, str( fac( n ) ) ) )
  
def prob20():
  assert facSum( 10 ) == 27
  return facSum( 100 )

def getFactorSum( n ):
  sum = 1
  for i in range( 2, n / 2 + 1 ):
    if not n % i:
      sum += i
  return sum
  
def prob21():
  fss = dict( [ ( i, getFactorSum( i ) ) for i in range( 1, 10001 ) ] )
  assert fss[fss[220]] == 220
  assert fss[fss[284]] == 284
  sum = 0
  for i, fs in fss.iteritems():
    if fs != i and fs in fss and fss[fs] == i:
      sum += i
  return sum

def getNameScore( name ):
  return sum( [ ord(c) - ord('a') + 1 for c in name ] )
  
def prob22():
  names = sorted( [ name.strip( '"' ).lower() for name in open( 'names.txt' ).read().split(',') ] )
  return sum( [ ( i + 1 ) * getNameScore( name ) for i, name in enumerate( names )  ] )

def isAbundant( n ):
  return getFactorSum( n ) > n
  
def addsTo( n, adders ):
  nadders = filter( lambda a: a < n, adders )
  for a in nadders:
    if n - a in nadders:
      return True
  return False

def getSums( l ):
  sums = set()
  for i in range( len( l ) ):
    for j in range( i, len( l ) ):
      sums.add( l[i] + l[j] )
  return sums
  
def prob23():
  abundantNums = filter( isAbundant, range( 1, 28124 ) )
  sums = getSums( abundantNums )
  return sum( filter( lambda i: i not in sums, range( 1, 28124 ) ) )

def permute( l ):
  if not l:
    return [[]]
  else:
    r = []
    for i in range( len( l ) ):
      for pi in permute( l[:i] + l[i+1:] ):
        r.append( [l[i]] + pi )
    return r
    
def prob24():
  assert [2,1,0] == sorted( permute( range( 3 ) ) )[5]
  perms = sorted( list( set( [ ''.join( map( str, perm ) ) for perm in permute( range( 10 ) ) ] ) ) )
  assert len( perms ) == fac( 10 )
  assert all( [ perms[i] < perms[i+1] for i in range( len( perms) - 1 ) ] )
  return perms[999999] #lame
  
def prob25():
  a = 1
  b = 1
  i = 2
  while len( str( b ) ) < 1000:
    c = a + b
    a = b
    b = c
    i += 1
  return i

def decimalExpansion( num, denom, n ):
  s = ''
  for i in range( n ):
    s += str( int( num / denom ) )
    num = ( num % denom ) * 10
  return s
  
def isCycle( s, n ):
  return all( [ s[i*n:(i+1)*n] == s[:n] for i in range( len( s ) / n ) ] )
  
def cycleLength( s ):
  cls = filter( lambda i: isCycle( s, i ), range( 1, len( s ) / 2 + 1 ) )
  if cls:
    return min( cls )
  else:
    return 0
    
def recipCycleLength( denom ):
  s = decimalExpansion( 1., denom, 2000 )
  cls = [ cycleLength( s[i:] ) for i in range( 10 ) ]
  if cls:
    return max( cls )
  else:
    return 0
  
def prob26():
  assert recipCycleLength( 7 ) == 6
  return max( range( 1, 1000 ), key = recipCycleLength )
  
def numQuadPrimes( a, b ):
  i = 0
  while isPrime( i * i + a * i + b ):
    i += 1
  return i
  
def prob27():
  assert numQuadPrimes( 1, 41 ) == 40
  assert numQuadPrimes( -79, 1601 ) == 80
  max = -1
  prod = -1
  for a in range( -999, 1000 ):
    for b in range( -999, 1000 ):
      n = numQuadPrimes( a, b )
      if n > max:
        max = n
        prod = a * b
  return prod

class Board:
  def __init__( self, n ):
    assert n % 2
    self.n = n
    self.board = [ 0 ] * self.n * self.n
    
  def __getitem__( self, ( i, j ) ):
    assert i < self.n and j < self.n
    return self.board[ j * self.n + i ]
    
  def __setitem__( self, ( i, j ), v ):
    assert i < self.n and j < self.n
    self.board[ j * self.n + i ] = v
    
  def __repr__( self ):
    return '\n'.join( map( str, [ self.board[ j * self.n : ( j + 1 ) * self.n ] for j in range( self.n ) ] ) )

  def fillSpiral( self ):
    mid = self.n / 2
    self[mid,mid] = 1
    v = 2
    for layer in range( 1, self.n / 2 + 1 ):
      for j in range( mid - layer + 1, mid + layer + 1 ):
        self[mid + layer, j] = v
        v += 1
      for i in range( mid + layer - 1, mid - layer - 1, -1 ):
        self[i, mid + layer] = v
        v += 1
      for j in range( mid + layer - 1, mid - layer - 1, -1 ):
        self[mid - layer, j ] = v
        v += 1
      for i in range( mid - layer + 1, mid + layer + 1 ):
        self[i, mid - layer] = v
        v += 1
    assert v == self.n * self.n + 1
    
  def fillReverseSpiral( self ):
    mid = self.n / 2
    self[mid,mid] = 1
    v = 2
    for layer in range( 1, self.n / 2 + 1 ):
      for j in range( mid + layer - 1, mid - layer - 1, -1 ):
        self[mid + layer, j] = v
        v += 1
      for i in range( mid + layer - 1, mid - layer - 1, -1 ):
        self[i, mid - layer] = v
        v += 1
      for j in range( mid - layer + 1, mid + layer + 1 ):
        self[mid - layer, j ] = v
        v += 1
      for i in range( mid - layer + 1, mid + layer + 1 ):
        self[i, mid + layer] = v
        v += 1
    assert v == self.n * self.n + 1
    
  def diags( self ):
    mid = self.n / 2
    return sum( [ [ self[i,i], self[self.n-i-1,i], self[i,self.n-i-1], self[self.n-i-1,self.n-i-1] ] for i in range(mid) ], [ self[mid,mid] ] )
        
  def diagSum( self ):
    return sum( self.diags() )
    
def prob28():
  b = Board( 5 )
  b.fillSpiral()
  assert 101 == b.diagSum()
  b = Board( 1001 )
  b.fillSpiral()
  return b.diagSum()

def prob29():
  s = set()
  for a in range( 2, 101 ):
    for b in range( 2, 101 ):
      s.add( a ** b )
  return len( s )

def prob30():
  s = 0
  for i in range( 2, 1000000 ):
    if i == sum( [ d ** 5 for d in map( int, str( i ) ) ] ):
      s += i
  return s

@memoize  
def coinPerms( n ):
  if n == 0:
    return [()]
  else:
    r = set()
    for i in ( 1, 2, 5, 10, 20, 50, 100, 200 ):
      if n >= i:
        for ri in coinPerms( n - i ):
          r.add( tuple( sorted( (i,) + ri ) ) )
    return r
  
def prob31():
  perms = list( coinPerms( 200 ) )
  assert all( [ sum( perm ) == 200 for perm in perms ] )
  return len( perms )

def splits( s ):
  return [ ( s[:l], s[l:] ) for l in range( 1, len( s ) ) ]
  
def prob32():
  prods = set()
  for perm in permute( range( 1, 10 ) ):
    permStr = ''.join( map( str, perm ) )
    for astr, bc in splits( permStr ):
      for bstr, cstr in splits( bc ):
        a, b, c = map( int, ( astr, bstr, cstr ) )
        if a * b == c:
          prods.add( c )
  return sum( prods )

def fracPerms( num, den ):
  n0 = int( str( num )[0] )
  n1 = int( str( num )[1] )
  d0 = int( str( den )[0] )
  d1 = int( str( den )[1] )
  if 0 != d0 and n1 != d1:
    l = []
    if n0 == d1:
      l.append( ( n1, d0 ) )
    if n1 == d0:
      l.append( ( n0, d1 ) )
    return l
  else:
    return []
  
def prob33():
  ns = []
  ds = []
  for den in range( 10, 100 ):
    for num in range( 10, den ):
      for n, d in fracPerms( num, den ):
        if d and float( num ) / float( den ) == float( n ) / float( d ):
          ns.append( n )
          ds.append( d )
  return product( ds ) / product( ns )

def prob34():
  s = 0
  for i in range( 3, 1000000 ):
    if i == sum( map( fac, map( int, str( i ) ) ) ):
      s += i
  return s

def isCircularPrime( n ):
  s = str( n )
  for i in range( len( s ) ):
    if not isPrime( int( s[i:] + s[:i] ) ):
      return False
  return True
  
def prob35():
  assert isCircularPrime( 197 )
  return sum( map( isCircularPrime, range( 2, 1000000 ) ) )

def isMultibasePalindrome( n ):
  return isPalindrome( str( n ) ) and isPalindrome( str( bin( n ) ).split( 'b' )[-1] )
  
def prob36():
  assert isMultibasePalindrome( 585 )
  return sum( filter( isMultibasePalindrome, range( 1000000 ) ) )

def isTruncatablePrime( n ):
  s = str( n )
  for i in range( len( s ) ):
    if not isPrime( int( s[i:] ) ) or ( i and not isPrime( int( s[:-i] ) ) ):
      return False
  return True
    
def prob37():
  assert isTruncatablePrime( 3797 )
  i = 8
  l = []
  while len( l ) < 11:
    if isTruncatablePrime( i ):
      l.append( i )
    i += 1
  return sum( l )

def concatProduct( n, l ):
  return ''.join( map( str, [ n * i for i in l ] ) )
  
def isPanDigital( s ):
  return ''.join( sorted( s ) ) == ''.join( map( str, range( 1, len( s ) + 1 ) ) )
  
def prob38():
  assert isPanDigital( concatProduct( 9, range( 1, 6 ) ) )
  assert isPanDigital( concatProduct( 192, range( 1, 4 ) ) )
  max = -1
  for i in range( 1, 1000000 ):
    j = 3
    s = concatProduct( i, range( 1, j ) )
    while len( s ) < 10:
      if len( s ) == 9 and isPanDigital( s ) and int( s ) > max:
        max = int( s )
      j += 1
      s = concatProduct( i, range( 1, j ) )
  return max

def numTris( p ):
  n = 0
  for i in range( 1, p ):
    for j in range( i + 1, p ):
      k = p - i - j
      if i * i + j * j == k * k:
        n += 1
  return n
  
def prob39():
  assert 3 == numTris( 120 )
  return max( range( 1001 ), key = numTris )
  
def prob40():
  s = ''
  i = 1
  while len( s ) < 1000000:
    s += str( i )
    i += 1
  return product( map( int, [ s[ 10 ** i - 1 ] for i in range( 7 ) ] ) )

def prob41():
  for l in range( 10, 0, -1 ):
    perms = map( int, [ ''.join( map( str, perm ) ) for perm in permute( range( 1, l ) ) ] )
    primes = filter( isPrime, perms )
    if primes:
      return max( primes )

tris = [1]
def isTri( n ):
  if n > tris[-1]:
    while tris[-1] < n:
      tris.append( tris[-1] + len( tris ) + 1 )
  return n in tris

def prob42():
  assert isTri( 55 )
  assert not isTri( 56 )
  words = [ word.strip( '"' ).lower() for word in open( 'words.txt' ).read().split( ',' ) ]
  scores = [ sum( [ ord( c ) - ord( 'a' ) + 1 for c in word ] ) for word in words ]
  return sum( map( isTri, scores ) )

def prob43():
  def cond( n ):
    s = str( n )
    def div( i, d ):
      return int( s[i-1:i+2] ) % d == 0
    return div( 2, 2 ) and div( 3, 3 ) and div( 4, 5 ) and div( 5, 7 ) and div( 6, 11 ) and div( 7, 13 ) and div( 8, 17 )
    
  assert cond( 1406357289 )
  perms = map( int, [ ''.join( map( str, perm ) ) for perm in permute( range( 10 ) ) ] )
  return sum( filter( cond, perms ) )

def prob44():
  pents = [ i * ( 3 * i - 1 ) / 2 for i in range( 1, 10000 ) ]
  pentSet = set( pents )
  l = []
  for i in range( len( pents ) ):
    for j in range( i ):
      d = pents[i] - pents[j]
      s = pents[i] + pents[j]
      if d in pentSet and s in pentSet:
        l.append( d )
  return min( l )

pents = [1]
def isPent( n ):
  while n > pents[-1]:
    i = len( pents ) + 1
    pents.append( i * ( 3 * i - 1 ) / 2 )
  return n in pents
  
hexes = [1]
def isHex( n ):
  while n > hexes[-1]:
    i = len( hexes ) + 1
    hexes.append( i * ( 2 * i - 1 ) )
  return n in hexes
  
def prob45():
  assert isTri( 40755 ) and isPent( 40755 ) and isHex( 40755 )
  i = 1
  n = 1
  l = []
  while len( l ) < 3:
    if isPent( n ) and isHex( n ):
      l.append( n )
    i += 1
    n += i
  return l[-1]
  
def isComposite( n ):
  return any( [ n % i == 0 for i in range( 2, n ) ] )
  
def isGoldbach( n ):
  for i in filter( isPrime, range( 1, n ) ):
    j = 1
    c = 2 * j * j + i
    while c < n:
      j += 1
      c = 2 * j * j + i
    if c == n:
      return True
  return False

def prob46():
  assert all( map( isGoldbach, ( 9, 15, 21, 25, 27, 33 ) ) )
  i = 1
  while not ( i % 2 and isComposite( i ) and not isGoldbach( i ) ):
    i += 1
  return i

@memoize
def getNumPrimeFactors( n ):
  c = 0
  for i in range( 2, n / 2 + 1 ):
    if not n % i and not getNumPrimeFactors( i ):
      c += 1
  return c
  
def prob47():
  def find( n ):
    i = 1
    while not all( [ getNumPrimeFactors( i + j ) == n for j in range( n ) ] ):
      i += 1
    return i
  assert find( 2 ) == 14
  assert find( 3 ) == 644
  return find( 4 )

def prob48():
  return str( sum( [ i ** i for i in range( 1, 1001 ) ] ) )[-10:]
  
def isPermutation( a, b ):
  return sorted( a ) == sorted( b )
  
def arePermutations( l ):
  return all( [ isPermutation( l[0], l[i] ) for i in range( 1, len( l ) ) ] )

def isPrime2( n ):
  return not getNumPrimeFactors( n )
  
def prob49():
  def cond( a, b ):
    n = [ a + b * i for i in range( 3 ) ]
    if arePermutations( map( str, n ) ) and all( map( isPrime, n ) ):
      return ''.join( map( str, n ) )
  assert cond( 1487, 3330 ) == '148748178147'
  for a in range( 1000, 10000 ):
    for b in range( 1000, ( 10000 - a ) / 2 ):
      s = cond( a, b )
      if s and ( a, b ) != ( 1487, 3330 ):
        return s

def prob50():
  def cond( n ):
    primes = filter( isPrime, range( 1, n ) )
    l = []
    for i in range( len( primes ) ):
      j = i
      s = primes[j]
      while s < n and j < len( primes ) - 1:
        if isPrime( s ):
          l.append( primes[i:j+1] )
        j += 1
        s += primes[j]
    return sum( max( l, key = len ) )
  assert cond( 100 ) == 41
  assert cond( 1000 ) == 953
  return cond( 1000000 )

def prob51():
  def replaceDigits( s, perm ):
    r = []
    for i in range( 10 ):
      if i or not perm[0]:
        si = ''
        for j in range( len( s ) ):
          if perm[j]:
            si += str( i )
          else:
            si += s[j]
        r.append( si )
    return r
    
  @memoize
  def replacementPerms( n ):
    perms = set()
    for l in range( 1, n + 1 ):
      for perm in permute( [1] * l + [0] * ( n - l ) ):
        perms.add( tuple( perm ) )
    return perms

  def primeFamily( n ):
    s = str( n )
    r = []
    for perm in replacementPerms( len( s ) ):
      r.append( filter( isPrime, map( int, replaceDigits( s, perm ) ) ) )
    return max( r, key = len )
    
  assert len( primeFamily( 13 ) ) == 6
  assert len( primeFamily( 56003 ) ) == 7
  
  i = 10
  while True:
    if isPrime( i ):
      pf = primeFamily( i )
      if len( pf ) == 8:
        return min( pf )
    i += 1

def prob52():
  def cond( n, m ):
    return arePermutations( map( str, [ n * i for i in range( 2, m + 1 ) ] ) )
    
  assert cond( 125874, 2 )

  i = 1
  while not cond( i, 6 ):
    i += 1
  return i

def prob53():
  def c( n, r ):
    return fac( n ) / ( fac( r ) * fac( n - r ) )
    
  assert c( 23, 10 ) == 1144066
  
  s = 0
  for n in range( 1, 101 ):
    for r in range( 1, n ):
      if c( n, r ) > 1000000:
        s += 1
  return s
  
def prob54():
  class Card:
    def __init__( self, rank, suit ):
      assert rank >= 2 and rank <= 14, 'invalid rank %d' % rank
      assert suit in 'hdsc', 'invalid suit %s' % suit
      self.rank = rank
      self.suit = suit
      
    def __repr__( self ):
      return '%s%s' % ( self.rank, self.suit )
      
    def __eq__( self, c ):
      return self.rank == c.rank and self.suit == c.suit
      
    suitRanks = dict( s = 4, h = 3, c = 2, d = 1 )
      
    def __lt__( self, c ):
      if self.rank < c.rank:
        return True
      elif self.rank == c.rank:
        return Card.suitRanks[ self.suit ] < Card.suitRanks[ c.suit ]
      else:
        return False

    paint = dict( t = 10, j = 11, q = 12, k = 13, a = 14 )
      
    @staticmethod
    def parse( s ):
      assert len( s ) == 2, 'invalid card str %s' % s
      rs = s[0]
      if rs in Card.paint:
        r = Card.paint[rs]
      else:
        r = int( rs )
      return Card( r, s[1] )

  class Hand:
    def __init__( self, cards ):
      assert len( cards ) == 5
      self.cards = sorted( cards )

    def __repr__( self ):
      return str( self.cards )
      
    def __lt__( self, h ):
      ht, inv = self.getHandType()
      hht, hinv = h.getHandType()
      if ht < hht:
        return True
      elif ht == hht:
        for c, hc in zip( sorted( inv, reverse = True ), sorted( hinv, reverse = True ) ):
          if c < hc:
            return True
          elif c > hc:
            return False
        assert 0
      else:
        return False
      
    @staticmethod
    def parse( s ):
      return Hand( map( Card.parse, s.lower().split() ) )
      
    def getSets( self ):
      sets = [[self.cards[0]]]
      for card in self.cards[1:]:
        if card.rank == sets[-1][-1].rank:
          sets[-1].append( card )
        else:
          sets.append( [card] )
      return sorted( sets, key = len, reverse = True )
      
    def getSetsOfSize( self, n ):
      return filter( lambda set: len( set ) == n, self.getSets() )
      
    def fourOfAKind( self ):
      sets = self.getSetsOfSize( 4 )
      if sets:
        return sets[0]
      
    def twoPair( self ):
      sets = self.getSetsOfSize( 2 )
      if len( sets ) == 2:
        return sum( sets, [] )
      
    def pair( self ):
      sets = self.getSetsOfSize( 2 )
      if len( sets ) == 1:
        return sets[0]
        
    def threeOfAKind( self ):
      sets = self.getSetsOfSize( 3 )
      if sets:
        return sets[0]
        
    def fullHouse( self ):
      sets = self.getSets()
      if map( len, sets ) == [ 3, 2 ]:
        return sum( sets, [] )
      
    def flush( self ):
      if all( [ self.cards[0].suit == card.suit for card in self.cards[1:] ] ):
        return self.cards
      
    def straight( self ):
      if all( [ self.cards[i].rank + 1 == self.cards[i+1].rank for i in range( len( self.cards ) - 1 ) ] ):
        return self.cards
      
    def straightFlush( self ):
      if self.straight() and self.flush():
        return self.cards
      
    def royalFlush( self ):
      if self.straightFlush() and self.cards[0].rank == 10:
        return self.cards
        
    def highCard( self ):
      return self.cards[-1:]
        
    handTypes = [ royalFlush, straightFlush, fourOfAKind, fullHouse, flush, straight, threeOfAKind, twoPair, pair, highCard ]
        
    def getHandType( self ):
      for i, handType in enumerate( Hand.handTypes ):
        inv = handType( self )
        if inv:
          return len( Hand.handTypes ) - i, inv
      assert 0
          
    @staticmethod
    def getHandTypeName( i ):
      return Hand.handTypes[ len( Hand.handTypes ) - i ].__name__
      
    @staticmethod
    def test():
      handTypeData = [
        ( '2h 4c kd 8s ac', 'highCard', 'ac' ),
        ( '2h 2c 4c 6d 8s', 'pair', '2h 2c' ),
        ( '3h 3d 9s 9d kd', 'twoPair', '3h 3d 9s 9d' ),
        ( '2h 4h 4s 4d qd', 'threeOfAKind', '4h 4s 4d' ),
        ( '4h 5d 6c 7d 8s', 'straight', '' ),
        ( '2h 6h 7h 9h qh', 'flush', '' ),
        ( '6h 8d 8h 6s 6d', 'fullHouse', '' ),
        ( '8d 8h jd 8s 8c', 'fourOfAKind', '8h 8d 8c 8s' ),
        ( '7h 8h 9h th jh', 'straightFlush', '' ),
        ( 'ts js qs ks as', 'royalFlush', '' ),
      ]
      for handStr, typeStr, involvedStr_ in handTypeData:
        involvedStr = involvedStr_ or handStr
        ht, involved = Hand.parse( handStr ).getHandType()
        assert Hand.getHandTypeName( ht ) == typeStr
        expInvolved = sorted( map( Card.parse, involvedStr.split() ) )
        assert involved == expInvolved
        
      compData = [
        ( '2h 4c kd 8s ac', '2h 4c kd 8s as', 1 ),
        ( '2h 4c kd 8s ac', '2h 2c kd 8s ac', 1 ),
      ]
      for cd in compData:
        expWin = cd[-1]
        hands = map( Hand.parse, cd[:-1] )
        win = max( range( len( hands ) ), key = hands.__getitem__ )
        assert win == expWin, 'expected %s to win but %s won' % ( hands[expWin], hands[win] )
      
  Hand.test()
  
  wins = 0
  for line in open( 'poker.txt' ).readlines():
    toks = line.split()
    h1 = Hand.parse( ' '.join( toks[:5] ) )
    h2 = Hand.parse( ' '.join( toks[-5:] ) )
    if h2 < h1:
      wins += 1
  return wins

def prob55():
  def cond( n ):
    i = 0
    while i < 50:
      n = n + int( str( n )[::-1] )
      if isPalindrome( str( n ) ):
        return False
      i += 1
    return True
  assert not cond( 47 )
  assert not cond( 349 )
  assert cond( 4994 )
  return sum( map( cond, range( 1, 10000 ) ) )
  
def prob56():
  l = []
  for a in range( 1, 100 ):
    for b in range( 1, 100 ):
      l.append( sum( map( int, str( a ** b ) ) ) )
  return max( l )
  
def prob57():
  def add( w, n, d ):
    r = w * d + n, d
    return r
    
  def comp( l ):
    n, d = 2, 1
    for i in range( l - 1 ):
      n, d = add( 2, d, n )
    return add( 1, d, n )
      
  assert map( comp, range( 1, 5 ) ) == [ ( 3, 2 ), ( 7, 5 ), ( 17, 12 ), ( 41, 29 ) ]
  return sum( map( lambda (n,d): len( str( n ) ) > len( str( d ) ), map( comp, range( 1, 1001 ) ) ) )

def prob58():
  @memoize
  def getDiags( n ):
    if n == 1:
      return (1,), ()
    else:
      diags, primes = map( list, getDiags( n - 1 ) )
      for i in range( 4 ):
        diag = diags[-1] + ( n - 1 ) * 2
        diags.append( diag )
        if isPrime( diag ):
          primes.append( diag )
      return tuple( diags ), tuple( primes )
      
  assert getDiags( 4 ) == ( ( 1, 3, 5, 7, 9, 13, 17, 21, 25, 31, 37, 43, 49 ), ( 3, 5, 7, 13, 17, 31, 37, 43 ) )
    
  def getDiagPrimeFrac( n ):
    diags, primes = getDiags( n )
    return float( len( primes ) ) / float( len( diags ) )
    
  i = 2
  while getDiagPrimeFrac( i ) >= 0.1:
    i += 1
  return i * 2 - 1
  
def prob59():
  def decrypt( key, cipherText ):
    text = ''
    ki = 0
    for c in cipherText:
      text += chr( c ^ ord( key[ki] ) )
      ki = ( ki + 1 ) % len( key )
    return text
    
  def loadDict( pattern ):
    import glob
    d = set()
    for filename in glob.glob( pattern ):
      d = d.union( set( map( str.lower, open( filename ).read().split() ) ) )
    return d
    
  def genKeys( l ):
    if l == 0:
      return [ '' ]
    else:
      r = []
      for base in [ chr( ord( 'a' ) + i ) for i in range( 26 ) ]:
        for tail in genKeys( l - 1 ):
          r.append( base + tail )
      return r
    
  d = loadDict( 'english*' )
  lend = {}
  for i in d:
    l = len( i )
    if l in lend:
      lend[l].add( i )
    else:
      lend[l] = set( [i] )
      
  cipherText = map( int, open( 'cipher1.txt' ).read().split(',') )
  
  def numWords( text ):
    nw = 0
    for l, words in lend.iteritems():
      for p in range( len( text ) - l ):
        if text[p:p+l].lower() in words:
          nw += 1
    return nw

  key = max( genKeys( 3 ), key = lambda k: numWords( decrypt( k, cipherText[:50] ) ) )
  text = decrypt( key, cipherText )
  return sum( map( ord, text ) )
  
def enumerateSubsets( l, n, unique = False ):
  if n == 0:
    return [[]]
  elif len( l ) < n:
    return []
  else:
    r = enumerateSubsets( l[1:], n )
    for tail in enumerateSubsets( l[1:], n - 1 ):
      r.append( l[:1] + tail )
    return r
    
def prob60():
  def cond( l, i ):
    for j in l:
      si = str( i )
      sj = str( j )
      if not isPrime( int( si + sj ) ) or not isPrime( int( sj + si ) ):
        return False
    return True
    
  def search( l, currentSet, currentPos, n ):
    if n == 0:
      return currentSet
    else:
      for j in range( currentPos + 1, len( l ) - n ):
        if cond( currentSet, l[j] ):
          r = search( l, currentSet + [l[j]], j, n - 1 )
          if r:
            return r
  
  primes = filter( isPrime, range( 1, 10000 ) )
  assert [ 3, 7, 109, 673 ] == search( primes, [], 0, 4 )
  return sum( search( primes, [], 0, 5 ) )
  
def inSeries( f, start = 1 ):
  s = set([start])
  li = [start]
  def closure( n ):
    while n > li[0]:
      i = f( len( s ) + 1 )
      li[0] = i
      s.add( i )
    return n in s
  return closure
  
def prob61():
  sers = [ inSeries( lambda n: n * ( n + 1 ) / 2 ),
           inSeries( lambda n: n * n ),
           inSeries( lambda n: n * ( 3 * n - 1 ) / 2 ),
           inSeries( lambda n: n * ( 2 * n - 1 ) ),
           inSeries( lambda n: n * ( 5 * n - 3 ) / 2 ),
           inSeries( lambda n: n * ( 3 * n - 2 ) ), 
         ]
          
  def cond( l, cs ):
    if not l:
      return True
    else:
      for i in range( len( cs ) ):
        if cs[i](l[0]):
          return cond( l[1:], cs[:i] + cs[1+i:] )
      return False
    
  assert cond( [ 8128, 2882 ], sers[:4] )
  assert cond( [ 8128, 2882, 8281 ], sers[:4] )
  
  def convert( l ):
    return [ int( l[i] + l[ ( i + 1 ) % len( l ) ] ) for i in range( len( l ) ) ]
  
  def search( n, l, cs ):
    ns = convert( l )
    if cond( ns[:-1], cs ):
      if not n:
        if cond( ns, cs ):
          return ns
      else:
        for i in range( 10, 100 ):
          r = search( n - 1, l + [ str( i ) ], cs )
          if r: 
            return r
            
  assert sum( [ 8128, 2882, 8281 ] ) == sum( search( 3, [], sers[:4] ) )
  return sum( search( 6, [], sers ) )

#slow
def prob62():
  perms = []
  i = 1
  while True:
    c = i ** 3
    found = False
    for perm in perms:
      if isPermutation( str( perm[0] ), str( c ) ):
        found = True
        perm.append( c )
        if len( perm ) == 5:
          return min( perm )
    if not found:
      perms.append( [c] )
    i += 1

def prob63():
  n = 0
  for i in range( 100 ):
    j = 1
    while len( str( j ** i ) ) < i:
      j += 1
    while len( str( j ** i ) ) == i:
      j += 1
      n += 1
  return n
  
def getRootIndices( n, c ):
  m = 0.
  d = 1.
  a0 = a = math.floor( math.sqrt( n ) )
  f = [ int( a0 ) ]
  for i in range( c - 1 ):
    m = d * a - m
    d = ( n - m * m ) / d
    if not d: break
    a = int( ( a0 + m ) / d )
    f.append( a )
  return f
  
def prob64():
  def isCycle( l, n ):
    return all( [ l[i*n:(i+1)*n] == l[:n] for i in range( 1, len( l ) / n ) ] )
    
  def period( n ):
    f = getRootIndices( n, 1001 )[1:]
    if not f:
      return 0
    else:
      return min( filter( lambda i: isCycle( f, i ), range( 1, len( f ) / 2 ) ) )
  
  assert 4 == sum( map( lambda i: period( i ) % 2, range( 2, 14 ) ) )
  return sum( map( lambda i: period( i ) % 2, range( 2, 10001 ) ) )

def prob65():
  def calc( l ):
    n, d = l[-1], 1
    for j in l[:-1][::-1]:
      n, d = add( j, d, n )
    return n, d
    
  l = [2] + sum( [ [ 1, i * 2, 1 ] for i in range( 1, 50 ) ], [] )
  assert [ ( 2, 1 ),
           ( 3, 1 ),
           ( 8, 3 ),
           ( 11, 4 ),
           ( 19, 7 ) ] == [ calc( l[:i] ) for i in range( 1, 6 ) ]
           
  def numSum( n ):
    return sum( map( int, str( calc( l[:n] )[0] ) ) )
    
  assert 17 == numSum( 10 )
  return numSum( 100 )
  
def getConvergent( n, i ):
  def add( w, n, d ):
    r = w * d + n, d
    return r
    
  def calc( l ):
    n, d = l[-1], 1
    for j in l[:-1][::-1]:
      n, d = add( j, d, n )
    return n, d

  return calc( getRootIndices( n, i ) )

def getConvergents( n, i ):
  return [ getConvergent( n, j ) for j in range( 1, i + 1 ) ]
  
def prob66():
  isSquare = inSeries( lambda n: n * n )

  def solve( d ):
    i = 1
    while True:
      x, y = getConvergent( d, i )
      c = x * x - d * y * y
      if c == 1:
        return x
      i += 1
        
  assert [ 3, 2, 9, 5, 8 ] == map( solve, filter( lambda n: not isSquare( n ), range( 2, 8 ) ) )
  return max( filter( lambda n: not isSquare( n ), range( 1, 1001 ) ), key = solve )
  
def prob67():
  tri = [ map( int, line.split() ) for line in open( 'triangle.txt' ).readlines() ]
  tri = tuple( map( tuple, tri ) )
  
  @memoize
  def triMaxSum2( tri, i, j ):
    if i == len( tri ) - 1:
      return tri[i][j]
    else:
      return tri[i][j] + max( triMaxSum2( tri, i + 1, j ), triMaxSum2( tri, i + 1, j + 1 ) )
    
  return triMaxSum2( tri, 0, 0 )

def prob68():
  def cond( ring ):
    r0 = sum( ring[0] )
    return all( [ r0 == sum( r ) for r in ring[1:] ] )
    
  def toStr( ring ):
    s = ''
    i = min( range( len( ring ) ), key = lambda i: ring[i][0] )
    for j in range( len( ring ) ):
      s += ''.join( map( str, ring[ ( i + j ) % len( ring ) ] ) )
    return s
    
  def search( n, maxLen = None ):
    res = set()
    for perm in permute( range( 1, n * 2 + 1 ) ):
      ring = []
      for i in range( n ):
        ring.append( ( perm[ i * 2 ], perm[ i * 2 + 1 ], perm[ ( ( i + 1 ) * 2 + 1 ) % len( perm ) ] ) )
      if cond( ring ):
        s = toStr( ring )
        if not maxLen or len( s ) <= maxLen:
          res.add( s )
    return max( map( int, res ) )
    
  assert 432621513 == search( 3 )
  return search( 5, 16 )
  
def prob69():
  def comp( n ):
    lp = 1
    p = 1
    i = 1
    while p < n:
      while not isPrime( i ):
        i += 1
      lp = p
      p *= i
      i += 1
    return lp

  assert comp( 10 ) == 6
  return comp( 1000000 )

def genPrimes( min, max ):
  d = {}
  q = 2
  l = []
  while q < max:
    if q in d:
      for p in d[q]:
        d.setdefault( p + q, [] ).append( p )
      d.pop( q )
    else:
      if q >= min:
        l.append( q )
      d[ q * q ] = [q]
    q += 1
  return l
  
def prob70():
  max = 10 ** 7
  root = int( math.sqrt( max ) )
  primes = list( genPrimes( root / 2, root * 2 ) )
  best = None
  for i in range( len( primes ) ):
    for j in range( i + 1, len( primes ) ):
      n = primes[i] * primes[j]
      if n <= max:
        #doesn't work due to float accuracy
        #p = int( n * product( [ 1 - 1 / float( k ) for k in ( primes[i], primes[j] ) ] ) )
        p = ( primes[i] - 1 ) * ( primes[j] - 1 )
        r = n / float( p )
        if isPermutation( str( p ), str( n ) ) and ( best == None or r < best ):
          best = r
          bestn = n
  return bestn
  
def prob71():
  def comp( c ):
    tn = 3
    td = 7
    bn = 0
    bd = 1
    for d in range( 1, c + 1 ):
      fn = tn * d / float( td )
      for n in range( int( fn ), int( fn ) + 2 ):
        if n * td < tn * d and n * bd > bn * d:
          bn = n
          bd = d
    return bn
    
  assert comp( 8 ) == 2
  return comp( 1000000 )

def prob72():
  def comp( n ):
    phi = range( n + 1 )
    r = 0
    for i in range( 2, n + 1 ):
      if phi[i] == i:
        for j in range( i, n + 1, i ):
          o = phi[j]
          phi[j] = int( phi[j] * ( 1 - 1 / float( i ) ) )
      r += phi[i]
    return r
    
  assert comp( 8 ) == 21
  return comp( 1000000 )
    
def gcd( a, b ):
  while b:
    a, b = b, a % b
  return a
  
def prob73():
  def comp( c ):
    start = ( 1, 3 )
    stop = ( 1, 2 )
    r = 0
    for d in range( 2, c + 1 ):
      for n in range( int( start[0] * d / float( start[1] ) ), int( stop[0] * d / float( stop[1] ) ) + 2 ):
        if n * start[1] > start[0] * d and n * stop[1] < stop[0] * d and gcd( n, d ) == 1:
          r += 1
    return r
  assert comp( 8 ) == 3
  return comp( 12000 )
  
def prob74():
  facs = [ fac( i ) for i in range( 10 ) ]
      
  def f( n ):
    return sum( [ facs[ int( i ) ] for i in str( n ) ] )

  def count( n ):
    l = set([n])
    i = f(n)
    while i not in l:
      l.add( i )
      i = f( i )
    return len( l )
    
  assert f( 145 ) == 145
  assert count( 540 ) == 2
  assert count( 78 ) == 4
  assert count( 69 ) == 5
  return sum( [ count( i ) == 60 for i in range( 1000000 ) ] )
  
def prob75():
  def e( m, n, k ):
    m2 = m * m
    n2 = n * n
    return tuple( sorted( [ k * ( m2 - n2 ), k * 2 * m * n, k * ( m2 + n2 ) ] ) )
    
  def gen( maxl ):
    l = set()
    m = 2
    while True:
      ll = len( l )
      n = 1
      while n < m:
        k = 1
        v = e( m, n, k )
        while v not in l and sum( v ) < maxl:
          l.add( v )
          k += 1
          v = e( m, n, k )
        n += 1
      if ll == len( l ):
        break
      m += 1
    return l
    
  def comp( n ):
    d = {}
    for v in gen( n ):
      l = sum( v )
      if l in d:
        d[l] += 1
      else:
        d[l] = 1
    return sum( [ v == 1 for v in d.itervalues() ] )
      
  assert comp( 50 ) == 6
  return comp( 1500000 )

def prob76():
  @memoize
  def comp( n, l = None ):
    if n == 0:
      return 1
    else:
      return sum( [ comp( n - i, i ) for i in range( 1, min( l or n - 1, n ) + 1 ) ] )

  assert comp( 5 ) == 6
  return comp( 100 )
  
def prob77():
  primes = [2]
  def primesTo( n ):
    while primes[-1] < n:
      i = primes[-1] + 1
      while not isPrime( i ):
        i += 1
      primes.append( i )
    l = []
    i = 0
    while i < len( primes ) and primes[i] <= n:
      l.append( primes[i] )
      i += 1
    return l
  
  @memoize
  def comp( n, l = None ):
    if n == 0:
      return 1
    else:
      return sum( [ comp( n - i, i ) for i in primesTo( min( l or n, n ) ) ] )
      
  assert comp( 10 ) == 5
  
  i = 2
  while comp( i ) < 5000:
    i += 1
  return i
  
def prob78():
  def pent( n ):
    return ( n * ( 3 * n - 1 ) ) / 2
    
  def genPent( n ):
    if n % 2:
      return pent( -( n / 2 ) - 1 )
    else:
      return pent( ( n / 2 ) + 1 )
      
  def sign( i ):
    if i % 4 < 2:
      return 1
    else:
      return -1

  ps = [1]
  n = 1
  while True:
    r = 0
    i = 0
    while True:
      k = genPent( i )
      if k > n:
        break
      r += sign( i ) * ps[n-k]
      i += 1
    if r % 1000000 == 0:
      return n
    ps.append( r )
    if n == 5: assert r == 7
    n += 1
  
def prob79():
  ks = open( 'keylog.txt' ).read().split()
  
  rels = set()
  for k in ks:
    for i in range( len( k ) - 1 ):
      for j in range( i + 1, len( k ) ):
        rels.add( k[i] + k[j] )
  rels = list( rels )
  
  def cond( s, ( l, r ), hard ):
    if hard:
      return l in s and r in s and s.index( l ) < s.rindex( r )
    else:
      return l not in s or r not in s or s.index( l ) < s.rindex( r )
  
  l = ['']
  while True:
    for s in l:
      if all( [ cond( s, rel, True ) for rel in rels ] ):
        return s
    nl = []
    for s in l:
      for i in map( str, range( 10 ) ):
        if i not in s:
          ns = s + i
          if all( [ cond( s, rel, False ) for rel in rels ] ):
            nl.append( ns )
    assert nl
    l = nl
    
def prob80():
  isSquare = inSeries( lambda n: n * n )
  
  def sqrt( n, digits ):
    n *= 10 ** ( 2 * digits )
    i = 0
    j = 10 ** digits
    while i != j:
      i = j
      j = ( i + ( n // i ) ) >> 1
    return j
    
  def comp( n ):
    return sum( map( int, str( sqrt( n, 100 ) )[:100] ) )
    
  assert comp( 2 ) == 475
  return sum( [ comp( i ) for i in range( 1, 101 ) if not isSquare( i ) ] )

def prob81():
  m = [ map( int, l.split( ',' ) ) for l in open( 'matrix.txt' ).readlines() ]
  w = len( m[0] )
  h = len( m )
  minVal = min( map( min, m ) )

  class Astar:
    def __init__( self, i, j, parent ):
      self.i = i
      self.j = j
      self.parent = parent
      self.localCost = m[self.j][self.i]
      self.costToTarget = ( w - self.i + h - self.j ) * minVal
      self.calcCost()
      
    def calcCost( self ):
      self.travelCost = self.localCost
      if self.parent:
        self.travelCost += self.parent.travelCost
      self.totalCost = self.travelCost + self.costToTarget
      
    def expand( self ):
      r = []
      if self.i < w - 1:
        r.append( Astar( self.i + 1, self.j, self ) )
      if self.j < h - 1:
        r.append( Astar( self.i, self.j + 1, self ) )
      return r
      
    def done( self ):
      return self.i == w - 1 and self.j == h - 1
      
    def samePos( self, n ):
      return self.i == n.i and self.j == n.j
      
    @staticmethod
    def search( start ):
      open = [ start ]
      closed = []
      while open:
        next = min( open, key = lambda n: n.totalCost )
        open.remove( next )
        closed.append( next )
        if next.done():
          return next
        else:
          for child in next.expand():
            if not any( [ child.samePos( n ) for n in closed ] ):
              found = False
              for n in open:
                if child.samePos( n ):
                  found = True
                  if child.travelCost < n.travelCost:
                    n.parent = next
                    n.calcCost()
              if not found:
                open.append( child )
      
  r = Astar.search( Astar( 0, 0, None ) ).travelCost
  assert r == 427337, r
  return r

  m = [ map( int, line.split(',') ) for line in open( 'matrix.txt' ).readlines() ]
  w = len( m[0] )
  h = len( m )
  
  @memoize
  def comp( i, j ):
    if i == w - 1 and j == h - 1:
      return m[i][j]
    else:
      r = []
      if i < w - 1:
        r.append( m[i][j] + comp( i + 1, j ) )
      if j < h - 1:
        r.append( m[i][j] + comp( i, j + 1 ) )
      return min( r )
      
  r = comp( 0, 0 )
  assert r == 427337
  return r
  
def prob82():
  m = [ map( int, l.split( ',' ) ) for l in open( 'matrix.txt' ).readlines() ]
  # m = [ map( int, l.split() ) for l in '''131	673	234	103	18
# 201	96	342	965	150
# 630	803	746	422	111
# 537	699	497	121	956
# 805	732	524	37	331'''.split( '\n' ) ]
  w = len( m[0] )
  h = len( m )
  minVal = min( map( min, m ) )

  class Astar:
    def __init__( self, i, j, parent ):
      self.i = i
      self.j = j
      self.parent = parent
      self.localCost = m[self.j][self.i]
      self.costToTarget = ( w - self.i ) * minVal
      self.calcCost()
      
    def calcCost( self ):
      self.travelCost = self.localCost
      if self.parent:
        self.travelCost += self.parent.travelCost
      self.totalCost = self.travelCost + self.costToTarget
      
    def expand( self ):
      r = []
      if self.i < w - 1:
        r.append( Astar( self.i + 1, self.j, self ) )
      if self.j < h - 1:
        r.append( Astar( self.i, self.j + 1, self ) )
      if self.j > 0:
        r.append( Astar( self.i, self.j - 1, self ) )
      return r
      
    def done( self ):
      return self.i == w - 1
      
    def samePos( self, n ):
      return self.i == n.i and self.j == n.j
      
    @staticmethod
    def search( start ):
      open = start
      closed = []
      while open:
        next = min( open, key = lambda n: n.totalCost )
        open.remove( next )
        closed.append( next )
        if next.done():
          return next
        else:
          for child in next.expand():
            if not any( [ child.samePos( n ) for n in closed ] ):
              found = False
              for n in open:
                if child.samePos( n ):
                  found = True
                  if child.travelCost < n.travelCost:
                    n.parent = next
                    n.calcCost()
              if not found:
                open.append( child )
      
  return Astar.search( [ Astar( 0, j, None ) for j in range( h ) ] ).travelCost

def prob83():
  m = [ map( int, l.split( ',' ) ) for l in open( 'matrix.txt' ).readlines() ]
  w = len( m[0] )
  h = len( m )
  minVal = min( map( min, m ) )

  class Astar:
    def __init__( self, i, j, parent ):
      self.i = i
      self.j = j
      self.parent = parent
      self.localCost = m[self.j][self.i]
      self.costToTarget = ( w - self.i + h - self.j ) * minVal
      self.calcCost()
      
    def calcCost( self ):
      self.travelCost = self.localCost
      if self.parent:
        self.travelCost += self.parent.travelCost
      self.totalCost = self.travelCost + self.costToTarget
      
    def expand( self ):
      r = []
      if self.i < w - 1:
        r.append( Astar( self.i + 1, self.j, self ) )
      if self.i > 0:
        r.append( Astar( self.i - 1, self.j, self ) )
      if self.j < h - 1:
        r.append( Astar( self.i, self.j + 1, self ) )
      if self.j > 0:
        r.append( Astar( self.i, self.j - 1, self ) )
      return r
      
    def done( self ):
      return self.i == w - 1 and self.j == h - 1
      
    def samePos( self, n ):
      return self.i == n.i and self.j == n.j
      
    @staticmethod
    def search( start ):
      open = [ start ]
      closed = []
      while open:
        next = min( open, key = lambda n: n.totalCost )
        open.remove( next )
        closed.append( next )
        if next.done():
          return next
        else:
          for child in next.expand():
            if not any( [ child.samePos( n ) for n in closed ] ):
              found = False
              for n in open:
                if child.samePos( n ):
                  found = True
                  if child.travelCost < n.travelCost:
                    n.parent = next
                    n.calcCost()
              if not found:
                open.append( child )
      
  return Astar.search( Astar( 0, 0, None ) ).travelCost
  
def prob84():
  import random
  
  board = '''
GO A1 CC1 A2 T1 R1 B1 CH1 B2 B3
JAIL C1 U1 C2 C3 R2 D1 CC2 D2 D3
FP E1 CH2 E2 E3 R3 F1 F2 U2 F3
G2J G1 G2 CC3 G3 R4 CH3 H1 T2 H2
  '''.split()
  
  def comp( dieSize, n ):
    i = 0
    c = [ 0 ] * len( board )
    for r in range( n ):
      i = ( i + random.randint( 1, dieSize ) + random.randint( 1, dieSize ) ) % len( board )
      if board[i] == 'G2J':
        i = board.index( 'JAIL' )
      elif board[i].startswith( 'CC' ):
        j = random.randint( 1, 16 )
        if j == 1:
          i = board.index( 'GO' )
        elif j == 2:
          i = board.index( 'JAIL' )
      elif board[i].startswith( 'CH' ):
        j = random.randint( 1, 16 )
        if j == 1:
          i = board.index( 'GO' )
        elif j == 2:
          i = board.index( 'JAIL' )
        elif j == 3:
          i = board.index( 'C1' )
        elif j == 4:
          i = board.index( 'E3' )
        elif j == 5:
          i = board.index( 'H2' )
        elif j == 6:
          i = board.index( 'R1' )
        elif j == 7 or j == 8:
          while not board[i].startswith( 'R' ):
            i = ( i + 1 ) % len( board )
        elif j == 9:
          while not board[i].startswith( 'U' ):
            i = ( i + 1 ) % len( board )
        elif j == 10:
          i -= 3
      c[i] += 1
    return ''.join( [ '%02d' % i for i in sorted( range( len( c ) ), key = c.__getitem__, reverse = True )[:3] ] )
    
  n = 1000000
  assert comp( 6, n ) == '102400'
  return comp( 4, n )
  
def prob85():
  def comp( w, h ):
    r = 0
    for i in range( 1, w + 1 ):
      for j in range( 1, h + 1 ):
        r += ( w + 1 - i ) * ( h + 1 - j )
    return r
      
  assert 18 == comp( 3, 2 )
  
  mind = None
  for w in range( 1, 100 ):
    for h in range( 1, 100 ):
      c = comp( w, h )
      d = abs( 2000000 - c )
      if not mind or d < mind:
        mind = d
        mina = w * h
  return mina
  
def prob86():
  isSquare = inSeries( lambda n: n * n )
  
  l = 1
  c = 0
  while True:
    for wh in range( 3, 2 * l + 1 ):
      if isSquare( l * l + wh * wh ):
        if wh <= l:
          c += wh / 2
        else:
          d = 1 + ( l - ( wh + 1 ) / 2 )
          c += d
        if c > 1000000:
          return l
    l += 1
    
def prob87():
  def comp( n ):
    primes = {}
    primes[2] = filter( isPrime, range( 2, int( math.sqrt( n ) ) + 1 ) )
    primes[3] = filter( lambda p: p <= int( n ** ( 1 / 3. ) ), primes[2] )
    primes[4] = filter( lambda p: p <= int( n ** ( 1 / 4. ) ), primes[3] )

    s = set()
    for p4 in primes[4]:
      for p3 in primes[3]:
        for p2 in primes[2]:
          v = p4 ** 4 + p3 ** 3 + p2 ** 2
          if v <= n:
            s.add( v )
    return len( s )
    
  assert comp( 50 ) == 4
  return comp( 50000000 )
  
def prob88():
  d = {}
  
  def calc( n, nf, l ):
    if len( l ) <= nf:
      i = 2
      p = product( l )
      s = sum( l )
      ll = len( l )
      np = p * i
      while np < n * 2:
        if ll >= 1:
          ns = s + i
          nl = ll + 1 + np - ns
          if nl <= n and ( not nl in d or ( nl in d and np < d[nl] ) ):
            d[nl] = np
        calc( n, nf, l + [ i ] )
        i += 1
        np = p * i

  def comp( n ):
    calc( n, int( math.log( n, 2 ) ), [] )
    return sum( set( d.values() ) )

  assert 61 == comp( 12 )
  return comp( 12000 )

if __name__ == '__main__':
  import sys, time
  assert len( sys.argv ) == 2, 'usage: %s <probnum>' % sys.argv[0]
  probnum = int( sys.argv[1] )
  fname = 'prob%d' % probnum
  assert fname in globals(), 'unknown probnum %d' % probnum
  f = globals()[fname]
  start = time.time()
  sol = f()
  print 'prob %d solution is' % probnum, sol
  t = time.time() - start
  print 'solution took %f secs' % t
  assert t < 60, 'prob %d took %f secs' % ( probnum, t )
